import os
import random

def generate_tree(n):
    """Generate a random tree structure as a list of edges."""
    edges = []
    # Using a random spanning tree approach by connecting nodes in a chain and randomly adding nodes
    nodes = list(range(1, n + 1))
    random.shuffle(nodes)
    
    for i in range(1, n):
        # Connect each node to a random previous node to ensure a connected tree
        u = nodes[i]
        v = nodes[random.randint(0, i - 1)]
        edges.append((u, v))
    
    return edges

def generate_test_files(num_files, input_directory):
    # Ensure the output directory exists
    os.makedirs(input_directory, exist_ok=True)

    for i in range(1, num_files + 1):
        # Randomly choose the number of nodes for each test case within a reasonable range
        n = random.randint(25, 800)  # Adjust this for smaller-scale tests; scale up if needed

        # Generate a random tree for `n` nodes
        edges = generate_tree(n)

        # File paths for each test case
        input_file_path = os.path.join(input_directory, f"{i}.in")

        # Write the test case to an input file
        with open(input_file_path, "w") as f_in:
            f_in.write(f"{n}\n")
            for u, v in edges:
                f_in.write(f"{u} {v}\n")

        print(f"Generated test case {i} with {n} nodes and saved to {input_file_path}")

# Directory paths
input_directory = r"C:\Users\ASUS\Desktop\2024年新生赛出题\2024年新生赛出题(非大一组)\D题\D题_input"

# Generate 10 test files
generate_test_files(3, input_directory)
